package xyz.mydev.test;

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;

/**
 * @author ZSP
 */
public class TreeAssert2 {


  public static void main(String[] args) {


  }

  private static final Set<Node> REPEAT_SET = new HashSet<>();
  private static final Stack<Node> PATH_STACK = new Stack<>();
  private static final String Tree = "Tree";
  private static final String NonTree = "Non-tree";
  private static final String Circle = "Circle";


  /**
   * @return Tree/Non-tree/Circle
   */
  public static String assertGraphShape(Node root) {
    Objects.requireNonNull(root);
    return accessNode(root);
  }

  private static String accessNode(Node node) {
    if (node == null) {
      PATH_STACK.pop();
      return Tree;
    }

    String result = Tree;
    // 节点入set，入路径栈
    if (!REPEAT_SET.add(node)) {
      if (isCircleWithStack(node)) {
        return Circle;
      }
      result = NonTree;
    }
    PATH_STACK.push(node);
    String leftResult = accessNode(node.left);
    if (leftResult.equals(Circle)) {
      return Circle;
    } else {
      PATH_STACK.pop();
      result = leftResult.equals(NonTree) ? NonTree : result;
    }

    String rightResult = accessNode(node.right);
    if (rightResult.equals(Circle)) {
      return Circle;
    } else {
      PATH_STACK.pop();
      result = rightResult.equals(NonTree) ? NonTree : result;
    }

    return result;
  }

  /**
   * 看路径栈中是否有当前元素
   */
  private static boolean isCircleWithStack(Node node) {
    if (node == null) {
      return false;
    }
    return PATH_STACK.search(node) == -1;
  }
}

